1. Field of the Invention
The present invention relates generally to systems and methods for classifying time sequences, and particularly, to a system and method for making time-dependant class predictions.
2. Discussion of the Prior Art
Classification of time sequences has great utility in providing important predictability information for time sequences, and particularly, time-series data has great applicability in business. For example, the stock prices at the New York Stock Exchange are based on time-sequence behavior of the corresponding stocks. Such data has great use in providing important predictability information for time sequences.
Methods for mining sequential patterns in time series data have been proposed by Agrawal et al., in the reference xe2x80x9cMining Sequential Patterns,xe2x80x9d Proceedings of the Eleventh International Conference on Data Engineering (ICDE 95), pp. 3-14, (1995). These algorithms find the frequent time series which occur in these patterns. The algorithms discussed in this work are related to the large itemset mining methods proposed by Agrawal, Imielinski, and Swami in the reference entitled xe2x80x9cMining Association Rules Between Sets of Items in Large Databases,xe2x80x9d Proceedings of the ACM SIGMOD Conference on the Management of Data (SIGMOD 93), 207-216, Washington D.C., USA.
Methods for discovering frequent episodes in event sequences have been discussed in the reference entitled xe2x80x9cDiscovery of Frequent Episodes in Event Sequences,xe2x80x9d Data mining and Knowledge Discovery 1(3), pp. 259-289 by H. Mannila, H. Toivonen, A. I. Verkamo. In this work, frequent patterns of behavior (referred to as episodes) are detected by a computationally efficient data mining algorithm. Other work relating to pattern matching and predicting rare events in time sequences may be found in E. Keogh, and P. Smyth xe2x80x9cA Probabilistic Approach to Fast Pattern Matching in Time-Series Databases,xe2x80x9d Proceedings of the Knowledge Discovery and Data Mining Conference, 1997, and, in G. M. Weiss and H. Hirsh xe2x80x9cLearning to Predict Rare Events in Event Sequences,xe2x80x9d Proceedings of the Knowledge Discovery and Data Mining Conference, 1998 pages 359-363. Methods for mining and finding plan failures have been discussed in the reference entitled xe2x80x9cPLANMINE: Sequence Mining for Plan Failures,xe2x80x9d. Proceedings of the Knowledge Discovery and Data Mining Conference, 1998 pages 369-373 to M. J. Zaki, N. Lesh, M. Ogihara.
The above-mentioned references do not teach how to perform a time-dependant categorization given inputs of both feature variables that are a function of time and correspond to various time-dependant graphs and, time-dependant category variables which may take on one of several categorical values which and correspond to time-dependant graphs.
Thus, it would be highly desirable to provide a system and method for performing a time-dependant categorization, when both the feature variables and the category variables are time-dependant graphs.
The present invention is directed to a system and method for performing time-dependant classification of sequences which requires a finding of the frequent combinations of shapes which imply a given class variable at a given time-stamp.
According to the invention, there is provided a system and method for generating classification using time sequences comprising: receiving a set of time dependant feature variable graphs and a set of time dependant category variable graphs; finding frequent shapes in the time dependant feature variable graphs; utilizing the frequent shapes to generate combinations of frequent shapes; generating rules relating one or more patterns of combinations of frequent shapes to a category variable; and, performing a categorization utilizing the rules generated.
Advantageously, the present invention is useful for finding predictive relationships between the feature variables found in time dependant feature variable graphs and the class or category variable from corresponding time dependant category variable graphs.